#include <iostream>
#include <map>
#include <set>
#include <queue>
#include <list>
#include <string>
#include <string.h>

using namespace std;

struct edge {
	char vertex;
	char other_vertex;
	int weight;

	edge(char v1, char v2, int w) : vertex(v1), other_vertex(v2),
					weight(w) {}

	edge(const edge *e) : vertex(e->vertex), other_vertex(e->other_vertex),
			      weight(e->weight) {}
};

typedef list<edge*> edge_list_t;
typedef list<edge*>::iterator edge_list_iter_t;

set<char> processed;
set<char> toprocess;
map<char, list<edge*> > adjacency_list;

char vertices[] = "abcdefg";

class edge_comparison {
	public:
		edge_comparison() {}

		bool operator() (const edge *lhs, const edge *rhs)
		{
			return lhs->weight > rhs->weight;
		}
};
priority_queue<edge*, vector<edge*>, edge_comparison> edge_heap;

/* Iterate through the adjacency list of vertex. If any edge has the other side
 * in toprocess, add it to the heap */
void process(char vertex)
{
	edge_list_iter_t iter = adjacency_list[vertex].begin();

	toprocess.erase(vertex);
	processed.insert(vertex);

	cout << "Processing vertex: " << vertex << endl;
	while (iter != adjacency_list[vertex].end()) {
		edge *e = *iter;

		if (toprocess.find(e->vertex) != toprocess.end()) {
			cout << "Added (" << e->vertex << ", "
			     << e->other_vertex << ")" << " w: " << e->weight
			     << endl;
			edge_heap.push(new edge(*iter));
		} else {
			cout << "Not Added (" << e->vertex << ", "
			     << e->other_vertex << ")" << endl;
		}

		iter++;
	}
}


void init_adjacency_list(void)
{
	adjacency_list['a'].push_back(new edge('d', 'a', 5));
	adjacency_list['a'].push_back(new edge('b', 'a', 7));

	adjacency_list['b'].push_back(new edge('a', 'b', 7));
	adjacency_list['b'].push_back(new edge('c', 'b', 8));
	adjacency_list['b'].push_back(new edge('e', 'b', 7));
	adjacency_list['b'].push_back(new edge('d', 'b', 9));

	adjacency_list['c'].push_back(new edge('b', 'c', 8));
	adjacency_list['c'].push_back(new edge('e', 'c', 5));

	adjacency_list['d'].push_back(new edge('a', 'd', 5));
	adjacency_list['d'].push_back(new edge('b', 'd', 9));
	adjacency_list['d'].push_back(new edge('e', 'd', 15));
	adjacency_list['d'].push_back(new edge('f', 'd', 6));

	adjacency_list['e'].push_back(new edge('b', 'e', 7));
	adjacency_list['e'].push_back(new edge('c', 'e', 5));
	adjacency_list['e'].push_back(new edge('d', 'e', 15));
	adjacency_list['e'].push_back(new edge('f', 'e', 8));
	adjacency_list['e'].push_back(new edge('g', 'e', 9));

	adjacency_list['f'].push_back(new edge('d', 'f', 6));
	adjacency_list['f'].push_back(new edge('e', 'f', 8));
	adjacency_list['f'].push_back(new edge('g', 'f', 11));

	adjacency_list['g'].push_back(new edge('e', 'g', 9));
	adjacency_list['g'].push_back(new edge('f', 'g', 11));
}


int main(void)
{
	init_adjacency_list();
	for (int i = 0; i < strlen(vertices); i++)
		toprocess.insert(vertices[i]);

	cout << "Processing 1st element" << endl;
	process('d');

	cout << "Processing the rest of the graph" << endl;
	while(toprocess.empty() == false) {
		if (edge_heap.size() == 0) {
			cout << "Edge heap empty" << endl;
			break;
		}

		edge e(edge_heap.top());
		edge_heap.pop();

		if (processed.find(e.vertex) != processed.end()) {
			/* Do nothing. It has already been processed */
			cout << "Skipping " << e.vertex << " "
			     << e.other_vertex << endl;
		} else {
			cout << "\t\t\tPicked " << e.vertex << " "
			     << e.other_vertex << " Weight: " << e.weight
			     << endl;
			process(e.vertex);
		}
	}

	/* TODO: Free memory */
	return 0;
}

